package com.leetcode.动态规划.买卖股票的最佳时机;

/**
 * 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
 * 
 * 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
 * 
 * 返回获得利润的最大值。
 * 
 * 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
 * 
 * @author LZF
 *
 */
public class L714买卖股票的最佳时机含手续费 {
	public static void main(String[] args) {
		int result = maxProfit(new int[] {1, 3, 2, 8, 4, 9},2);
		System.out.println(result);
	}
	
	/**
	 * 两个状态：
	 * dp[i][0]:当天不持有股票所得的最高现金（前一天就不持有，或是今天卖出）
	 * dp[i][1]:当天持有股票所得的最高现金（前一天就持有，或是今天买入）
	 * 则，dp[i][0] = max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee)
	 * dp[i][1] = max(dp[i - 1][1],dp[i - 1][0] - prices[i])
	 * 初始化
	 * dp[0][0] = 0//当天并没有股票卖出，最后收入为0
	 * dp[0][1] = -prices[0]//当天持有，只能是当日买入
	 * @param prices
	 * @param fee
	 * @return
	 */
	public static int maxProfit(int[] prices, int fee) {
		int n = prices.length;
		if(n == 0) return 0;
		int[][] dp = new int[n][2];
		dp[0][1] = -prices[0];
		for(int i = 1;i < n;i++) {
			dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i] - fee);
			dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
		}
		return dp[n - 1][0];
	}
}
